#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType *elem; //整形指针，申请的堆空间起始地址存入elem
    int TableLen;   //存储动态数组里边元素的个数
}SSTable;
//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
//打印顺序表
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//快排核心函数：分割
//挖坑法
int Partition(ElemType *A,int low,int high)
{
    ElemType pivot=A[low]; //拿最左边的作为分割值，并存储
    while (low<high)
    {
        while (low<high&&A[high]>=pivot) //从后往前遍历找到一个比分割值小的
            high--;
        A[low]=A[high]; //把比分割值小的那个元素放到A[low]
        while (low<high&&A[low]<=pivot) //从前往后遍历找到一个比分割值大的
            low++;
        A[high]=A[low]; //把比分割值大的那个元素放到A[high]
    }
    A[low]=pivot; //把分割值放到中间位置，因为左边的刚好都比他小，右边都比他大
    return low;   //返回分割值所在下标
}
//快排
void QuickSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int pivot_pos=Partition(A,low,high);
        QuickSort(A,low,pivot_pos-1);
        QuickSort(A,pivot_pos+1,high);
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);
//    ElemType A[10]={64,94,95,79,69,84,18,22,12,78};
//    //内存copy接口，当你copy整型数组，或者浮点型时，使用memcpy，不能用strcpy，初试考memcpy概率很低
//    memcpy(ST.elem,A,sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    ST_Print(ST);
    QuickSort(ST.elem,0,9); //注意这个位置是n-1,也就是9，因为函数里取high的位置的值
    ST_Print(ST);
    return 0;
}
